#!/usr/bin/python
# -*- coding:utf-8 -*-
"""
python实现二分查找
"""


def binary_search(seq, num, lower=0, upper=None):
    """
    :param seq:
    :param num:
    :param lower:
    :param upper:
    :return:
    """
    if upper is None:
        upper = len(seq) - 1
    if lower == upper:
        if num == seq[upper]:
            return upper
        else:
            return None
    else:
        # 查找中间的索引
        middle = (lower + upper) // 2
        if num > seq[middle]:
            return binary_search(seq, num, middle, upper)
        elif num < seq[middle]:
            return binary_search(seq, num, lower, middle)
        else:
            return middle


if __name__ == "__main__":
    sequence = [1, 5, 9, 10, 12, 19, 35, 65, 88, 96]
    n = 19
    index = binary_search(sequence, n)
    print("查询到的索引为%d" % index)
